# 栈和 单调栈
# 队列和 优先队列， 双端队列（deque）：队首队尾都能入队出队

from collections import deque

nums = [1, 2, 3, 9, 5, 0, 6]

# 1. 找出数组中右边第一个比我小的元素代码实现(下标), 没有小于的默认 -1
def findMaxK(nums):
    """
        定义单调递增栈实现,里面使用下标，不使用下标的话，都不知道原数组谁大于谁了
        时间复杂度是O(2n), 最多遍历两边数组，一次入栈，一次出栈
    """
    stack = list()
    ans = [0]* len(nums)
    for i in range(len(nums)):
        if not stack or nums[i] > nums[stack[-1]]:
            stack.append(i)
        else:
            while stack and nums[stack[-1]] > nums[i]:
                ans[stack.pop()] = i
            stack.append(i)
        """
        可以直接优化if else为：
        while stack and nums[stack[-1]] > nums[i]:
                ans[stack.pop()] = i
            stack.append(i)
        """    
    # 清空栈中的元素
    while stack: ans[stack.pop()] = -1


# 2. 找出数组中右边离我最近的比我大的元素
def findMinK(nums):
    """
        同理，这里维护一个单调递减的栈
    """
    stack = list()
    ans = [0] * len(nums)
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            ans[stack.pop()] = i
        stack.append(i)

    while stack: ans[stack.pop()] = -1

    return ans

# 3.找出数组中左边离我最近的，比我小的元素
def findMinKLeft(nums):
    """
        同样维护一个单调递增栈，不过元素要逆序遍历
    """
    n = len(nums)
    ans = [0] * n
    stack = list()
    for i in range(n-1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            ans[stack.pop()] = i
        stack.append(i)
    
    # 最后的补 -1
    while stack: ans[stack.pop()] = -1

    return ans

# 4. 同理，找出数组中左边离我最近的，比我大的元素
def findMaxKLeft(nums):
    """
        同样维护一个单调递增栈，不过元素要逆序遍历
    """
    n = len(nums)
    ans = [0] * n
    stack = list()
    for i in range(n-1, -1, -1):
        while stack and nums[stack[-1]] < nums[i]:
            ans[stack.pop()] = i
        stack.append(i)
    
    # 最后的补 -1
    while stack: ans[stack.pop()] = -1

    return ans


"""
    上面的写法，规律是，栈顶元素和 当前元素i 进行比较，更新栈顶元素的最小或最大
    下面换种思路，按照相反的方向遍历， 规律是，栈顶元素和 当前元素比较，而更新的是当前元素
"""
# 第二种写法，找出右边第一个比我小的元素
def findMaxK2(nums):
    n = len(nums)
    # 默认右边没我小的，初始化为n
    ans = [n] * n
    stack = list()
    for i in range(n-1, -1, -1):
        # 1. 当前元素大于栈顶直接 pop()栈顶元素
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        # 2. 如果栈顶小于 当前元素，他就是右边最小的
        if stack and nums[stack[-1]] < nums[i]:
            ans[i] = stack[-1]
        # 3. 栈空直接进栈, 执行2， 当前元素也要进栈，他可能是下一个元素的最小元素
        stack.append(i)
    
    return ans

#  同理第二种方法，找出左边第一个比我小的
def findMinKLeft2(nums):
    n = len(nums)
    # 左边如果没有比当前元素小的，默认初始化为 -1
    ans = [-1] * n
    stack = list()
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        if stack and nums[stack[-1]] < nums[i]:
            ans[i] = stack[-1]
        stack.append(i)
    
    return ans


rst = findMinKLeft2(nums)
print(nums)
print(rst)

